from typing import *
from sortedcontainers import SortedSet


class Solution:
    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:
        n = len(accounts)

        p = [i for i in range(n)]

        email_p = {}

        def find(i):
            if p[i] != i:
                p[i] = find(p[i])
            return p[i]

        def merge(i, j):
            p[find(j)] = find(i)

        for i, account in enumerate(accounts):
            for j in range(1, len(account)):
                if account[j] in email_p:
                    merge(i, email_p[account[j]])
                else:
                    email_p[account[j]] = i
        id_emails = DefaultDict(SortedSet)
        for i, account in enumerate(accounts):
            for j in range(1, len(account)):
                id_emails[find(i)].add(account[j])
        ans = []
        visit = set()
        for i in range(n):
            pi = find(i)
            if pi not in visit:
                cur = [accounts[i][0]]
                cur.extend(id_emails[pi])
                ans.append(cur)
                visit.add(pi)
        return ans


class Solution:
    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:
        n = len(accounts)

        p = [i for i in range(n)]

        email_p = {}

        def find(i):
            if p[i] != i:
                p[i] = find(p[i])
            return p[i]

        def merge(i, j):
            p[find(j)] = find(i)

        for i, account in enumerate(accounts):
            for j in range(1, len(account)):
                if account[j] in email_p:
                    merge(i, email_p[account[j]])
                else:
                    email_p[account[j]] = i
        id_emails = DefaultDict(SortedSet)
        for i, account in enumerate(accounts):
            pi = find(i)
            for j in range(1, len(account)):
                id_emails[pi].add(account[j])
        ans = []
        for i, v in id_emails.items():
            ans.append([accounts[i][0]] + list(v))
        return ans


class Solution:
    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:
        n = len(accounts)

        # 并查集
        p = [i for i in range(n)]

        def find(i):
            if p[i] != i:
                p[i] = find(p[i])
            return p[i]

        def merge(i, j):
            p[find(j)] = find(i)

        # 根据email 合并账户
        email_p = {}
        for i, account in enumerate(accounts):
            for j in range(1, len(account)):
                if account[j] in email_p:
                    merge(i, email_p[account[j]])
                else:
                    email_p[account[j]] = i
        # 合并email到同一个账户的有序集
        id_emails = DefaultDict(SortedSet)
        for i, account in enumerate(accounts):
            for j in range(1, len(account)):
                id_emails[find(i)].add(account[j])

        # 按照 账户 + email列表方式整理答案
        return [[accounts[i][0]] + list(v) for i, v in id_emails.items()]


class Solution:
    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:
        n = len(accounts)

        # 并查集
        p = [i for i in range(n)]

        def find(i):
            if p[i] != i:
                p[i] = find(p[i])
            return p[i]

        def merge(i, j):
            p[find(j)] = find(i)

        # 根据email 合并账户
        email_p = {}
        for i, account in enumerate(accounts):
            for j in range(1, len(account)):
                if account[j] in email_p:
                    merge(i, email_p[account[j]])
                else:
                    email_p[account[j]] = i
        # 合并email到同一个账户的有序集
        id_emails = DefaultDict(SortedSet)
        for i, account in enumerate(accounts):
            for j in range(1, len(account)):
                id_emails[find(i)].add(account[j])

        # 按照 账户 + email列表方式整理答案
        return [[accounts[i][0]] + list(v) for i, v in id_emails.items()]


so = Solution()
print(
    so.accountsMerge(
        [
            ["John", "johnsmith@mail.com", "john_newyork@mail.com"],
            ["John", "johnsmith@mail.com", "john00@mail.com"],
            ["Mary", "mary@mail.com"],
            ["John", "johnnybravo@mail.com"],
        ]
    )
    == [
        ["John", "john00@mail.com", "john_newyork@mail.com", "johnsmith@mail.com"],
        ["Mary", "mary@mail.com"],
        ["John", "johnnybravo@mail.com"],
    ]
)

print(
    so.accountsMerge(
        [
            ["David", "David0@m.co", "David4@m.co", "David3@m.co"],
            ["David", "David5@m.co", "David5@m.co", "David0@m.co"],
            ["David", "David1@m.co", "David4@m.co", "David0@m.co"],
            ["David", "David0@m.co", "David1@m.co", "David3@m.co"],
            ["David", "David4@m.co", "David1@m.co", "David3@m.co"],
        ]
    )
    == [
        [
            "David",
            "David0@m.co",
            "David1@m.co",
            "David3@m.co",
            "David4@m.co",
            "David5@m.co",
        ]
    ]
)

# [
#     ["David", "David0@m.co", "David1@m.co", "David3@m.co", "David4@m.co"],
#     ["David", "David0@m.co", "David5@m.co"],
#     ["David", "David0@m.co", "David1@m.co", "David3@m.co"],
# ]


# [["David", "David0@m.co", "David1@m.co", "David3@m.co", "David4@m.co", "David5@m.co"]]


arr = [i for i in range(10) if i & 1 == 0]
print(arr)

